/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */

#ifndef BTREEINDEX_H
#define BTREEINDEX_H

#include "Bruinbase.h"
#include "PageFile.h"
#include "RecordFile.h"

#ifdef DEBUG
#include <iostream>
#include "BTreeNode.h"
using std::cout;
using std::endl;
#endif
             
/**
 * The data structure to point to a particular entry at a b+tree leaf node.
 * An IndexCursor consists of pid (PageId of the leaf node) and 
 * eid (the location of the index entry inside the node).
 * IndexCursor is used for index lookup and traversal.
 */
typedef struct {
  // PageId of the index entry
  PageId  pid;  
  // The entry number inside the node
  int     eid;  
} IndexCursor;

/**
 * Implements a B-Tree index for bruinbase.
 * 
 */
class BTreeIndex {
 public:
  BTreeIndex();

  /**
   * Open the index file in read or write mode.
   * Under 'w' mode, the index file should be created if it does not exist.
   * @param indexname[IN] the name of the index file
   * @param mode[IN] 'r' for read, 'w' for write
   * @return error code. 0 if no error
   */
  RC open(const std::string& indexname, char mode);

  /**
   * Close the index file.
   * @return error code. 0 if no error
   */
  RC close();
    
  /**
   * Insert (key, RecordId) pair to the index.
   * @param key[IN] the key for the value inserted into the index
   * @param rid[IN] the RecordId for the record being inserted into the index
   * @return error code. 0 if no error
   */
  RC insert(int key, const RecordId& rid);

  /**
   * Find the leaf-node index entry whose key value is larger than or
   * equal to searchKey and output its location (i.e., the page id of the node
   * and the entry number in the node) as "IndexCursor."
   * IndexCursor consists of pid (page id of the node that contains the 
   * searchKey) and eid (the entry number inside the node)
   * to indicate the location of a particular index entry in the B+tree.
   * Note that, for range queries, we need to scan the B+tree leaf nodes.
   * For example, if the query is "key > 1000", we should scan the leaf
   * nodes starting with the key value 1000. For this reason,
   * this function returns the location of the leaf node entry
   * for a given searchKey, instead of returning the RecordId
   * associated with the searchKey.
   * Using the returned "IndexCursor", you will have to call readForward()
   * to retrieve the actual (key, rid) pair from the index.
   * @param key[IN] the key to find
   * @param cursor[OUT] the cursor pointing to the first index entry
   * with the key value
   * @return error code. 0 if no error.
   */
  RC locate(int searchKey, IndexCursor& cursor);

  /**
   * Read the (key, rid) pair at the location specified by the index cursor,
   * and move foward the cursor to the next entry.
   * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
   * @param key[OUT] the key stored at the index cursor location
   * @param rid[OUT] the RecordId stored at the index cursor location
   * @return error code. 0 if no error
   */
  RC readForward(IndexCursor& cursor, int& key, RecordId& rid);
  
#ifdef DEBUG
  void getKeyRange(bool& first, PageId pid, int depth, int& low, int& high) {
    if (depth == 0) {
      RecordId rid;
      BTLeafNode btln;
      btln.read(pid, pf);
      if (first) {
        btln.readEntry(0, low, rid);
        btln.readEntry(btln.getKeyCount() - 1, high, rid);
        first = false;
      }
      int ll, hh;
      btln.readEntry(0, ll, rid);
      btln.readEntry(btln.getKeyCount() - 1, hh, rid);
      low = (ll < low) ? ll : low;
      high = (hh < high) ? hh : high;
      return;
    }

    // nonzero depth
    BTNonLeafNode btnln;
    btnln.read(pid, pf);
    int ll, hh;
    for (int i = 0; i < *(btnln.pKeyCount); i++) {
      if (first) {
        getKeyRange(first, btnln.pbtnle[i].pid, depth - 1, low, high);
        first = false;
      }
      else
        getKeyRange(first, btnln.pbtnle[i].pid, depth - 1, ll, hh);
    }
    getKeyRange(first, btnln.pLastPid[0], depth - 1, ll, hh);
  }

  void print(PageId pid = -1, int depth = -1) {
    if (pid == -1) {
      cout << "root at " << rootPid << endl;
      cout << "tree height is " << treeHeight << endl << endl;
      pid = rootPid;
    }
    if (depth == -1)
      depth = treeHeight - 1;
 
    if (pid == -1)
      return;

    if (depth == 0) {
      BTLeafNode btln;
      int key;
      RecordId rid;
      btln.read(pid, pf);
      cout << "Depth " << depth << " ";
      cout << "Leaf pid=" << pid;
      btln.readEntry(0, key, rid);
      cout << " Key range: " << key;
      btln.readEntry(btln.getKeyCount() - 1, key, rid);
      cout << " " << key << endl;
      //cout << "-- Begin level 0 -- " << endl;
      //btln.print();
      //cout << "-- End level 0 -- " << endl;
      return;
    }

    BTNonLeafNode btnln;
    btnln.read(pid, pf);

    cout << "Depth " << depth << " ";
    cout << "Nonleaf page is " << pid;
    bool first = true;
    int low, high;
    getKeyRange(first, pid, depth, low, high);
    cout << " range " << low << " " << high << endl << endl;
    //btnln.print();

    for (int i = 0; i < *(btnln.pKeyCount); i++) {
      cout << "-> " << i << ": key=" << btnln.pbtnle[i].key << ", pid=";
      cout << btnln.pbtnle[i].pid << "\t";
      if (depth != 1)
        cout << endl;
      print(btnln.pbtnle[i].pid, depth - 1);
    }
    cout << btnln.pLastPid[0] << ": key=" << btnln.pbtnle[0].key << ", pid=";
    cout << btnln.pbtnle[0].pid << "\t";
    if (depth != 1)
      cout << endl;
    print(btnln.pLastPid[0], depth - 1);

  }

  int countKeys(PageId pid = -1, int depth = -1) {
    if (pid == -1) {
      pid = rootPid;
      depth = treeHeight - 1;
    }
    
    if (depth == 0) {
      BTLeafNode btln;
      btln.read(pid, pf);
      return btln.getKeyCount();
    }

    BTNonLeafNode btnln;
    btnln.read(pid, pf);

    int count = 0;
    for (int i = 0; i < btnln.getKeyCount(); i++) {
      //BTLeafNode btln;
      //btln.read(btnln.pbtnle[i].pid, pf);
      //count += btln.getKeyCount();
      count += countKeys(btnln.pbtnle[i].pid, depth - 1);
    }
    //BTLeafNode btln;
    //btln.read(btnln.pLastPid[0], pf);
    //count += btln.getKeyCount();
    count += countKeys(btnln.pLastPid[0], depth - 1);
    return count;
  }
#endif

 private:
  /**
   * Recusive implementation of insert
   * @param key[IN] the key for the value inserted into the index
   * @param rid[IN] the RecordId for the record being inserted into the index
   * @param pid[IN] the current page in the tree
   * @param depth[IN] the current depth in the tree
   * @param newChild[OUT] whether a new child node was created
   * @param childKey[OUT] the child key of the new node
   * @param childPid[OUT] the pid of the new node
   * @return error code. 0 if no error
   */
  RC _insert(int key, const RecordId& rid, const PageId& pid, int depth, bool& newChild, int& childKey, PageId& childPid);

  /**
   * Recursive implementation of locate
   * @param searchKey[IN] the key to search for
   * @param cursor[OUT] cursor containing the location of the key pair
   * @param pid[IN] the current pid
   * @param depth[IN] the current depth in the tree
   */
  RC _locate(int searchKey, IndexCursor& cursor, const PageId& pid, int depth);

  // Write header page to disk
  RC flushHeaders();

  // For recursive functions, leaf nodes are at depth 0 and the root node
  // is at depth (treeHeight - 1)

  PageFile pf;         /// the PageFile used to store the actual b+tree in disk
  // PageFile structure:
  // Page 0: Stores headers - [rootPid][treeHeight]
  // All other pages: part of the B+ tree

  PageId   rootPid;    /// the PageId of the root node
  int      treeHeight; /// the height of the tree
  /// Note that the content of the above two variables will be gone when
  /// this class is destructed. Make sure to store the values of the two 
  /// variables in disk, so that they can be reconstructed when the index
  /// is opened again later.
};

#endif /* BTREEINDEX_H */
